package demo;

import java.util.*;

public class TreeDemo {

    //前序遍历  中->左->右
    public void before(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        System.out.print(treeNode.val);
        before(treeNode.left);
        before(treeNode.right);
    }

    /**
     * 迭代 前序遍历
     * 中 左 左边没有就 右边遍历
     *
     * @param treeNode
     */
    public void before1(TreeNode treeNode) {
        if (treeNode == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNode);
        while (!stack.empty()) {
            //根节点所有最左边 出栈并删除栈顶元素
            TreeNode pop = stack.pop();
            //将右边入
            if (pop.right != null) {
                stack.push(pop.right);
            }

            //将左边入
            if (pop.left != null) {
                stack.push(pop.left);
            }
            System.out.print(pop.val);
        }
    }

    /**
     * 迭代 前序遍历
     * 中 左 左边没有就 右边遍历
     *  右进 左再进
     * @param treeNode
     */
    public void before2(TreeNode treeNode) {
        if (treeNode == null) return;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.empty() || treeNode != null) {
            if (treeNode != null) {
                System.out.print(treeNode.val);
                stack.push(treeNode);
                treeNode = treeNode.left;
            } else {
                treeNode = stack.pop();
                treeNode = treeNode.right;
            }
        }
    }


    //中序遍历  左中右
    public void mid(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        mid(treeNode.left);
        System.out.print(treeNode.val);
        mid(treeNode.right);
    }

    //中序遍历  左中右
    public void mid1(TreeNode treeNode) {
        if (treeNode == null) return;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.empty() || treeNode != null) {
            if (treeNode != null) {
                stack.push(treeNode);
                treeNode = treeNode.left;
            } else {
                treeNode = stack.pop();
                System.out.print(treeNode.val);
                treeNode = treeNode.right;
            }
        }
    }

    //后序遍历 左右中
    public void after(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        after(treeNode.left);
        after(treeNode.right);
        System.out.print(treeNode.val);
    }

    //后序遍历 迭代
    public void after1(TreeNode treeNode) {

    }

    //翻转二叉树
    public TreeNode resver(TreeNode treeNode) {
        if (treeNode == null) {
            return null;
        }
        TreeNode temp = treeNode.left;
        treeNode.left = treeNode.right;
        treeNode.right = temp;
        //继续翻转左右节点
        resver(treeNode.left);
        resver(treeNode.right);
        return treeNode;
    }


    /**
     * 完美二叉树
     *
     * @param root
     */
    public void getWanMei(TreeNode root) {
        if (root == null) {
            return;
        }
        connectTwoNode(root.left, root.right);
    }

    private void connectTwoNode(TreeNode node1, TreeNode node2) {
        if (node1 == null || node2 == null) {
            return;
        }
        node1.next = node2;
        //有几种情况 左边连接右边
        connectTwoNode(node1.left, node1.right);
        connectTwoNode(node2.left, node2.right);
        //隔着连接 node1的右边 node2的左边
        connectTwoNode(node1.right, node2.left);
    }


    //树转成链表
    void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.left);
        flatten(root.right);
        //后序遍历位置
        // 1、左右子树已经被拉平成一条链表
        TreeNode left = root.left;
        TreeNode right = root.right;
        // 2、将左子树作为右子树
        root.right = left;
        root.left = null;
        // 3、将原先的右子树接到当前右子树的末端
        TreeNode p = left;
        //这里是为了找到末端
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }

    //最大二叉树 明确根节点需要做什么
    //
    //
    // 根节点需要是下面节点中最大的
    // 左子树是通过数组中最大值左边部分构造的最大二叉树
    // 右子树是通过数组中最大值右边部分的最大二叉树
    TreeNode constructMaximumBinaryTree(int[] nums) {
//        int max = Integer.MIN_VALUE;
//        int p = 0;
//        for (int i = 0; i < nums.length; i++) {
//                if(nums[i]>max){
//                    max = nums[i];
//                    p = i;
//                }
//        }
//        TreeNode root = new TreeNode();
//        //root是num的最大值
//        root.val = max;
//        //root.left是  0- 最大值的索引
//        root.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums,0,p));
//
//        //root.right是 最大值索引到末尾
//        root.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums,p+1,nums.length));

        return build(nums, 0, nums.length - 1);
    }


    TreeNode build(int[] nums, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        int max = Integer.MIN_VALUE;
        int p = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] > max) {
                max = nums[i];
                p = i;
            }
        }
        TreeNode root = new TreeNode();
        //root是num的最大值
        root.val = max;
        root.left = build(nums, lo, p - 1);
        root.right = build(nums, p + 1, hi - 1);
        return root;
    }

    //从前序 中序 还原二叉树
    TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildT(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    TreeNode buildT(int[] preorder, int preStart, int preEnd, int[] inorder, int instart, int endStart) {
        TreeNode root = new TreeNode();
        //?根节点要做什么 取前序的第一个即为根节点 看在中序的哪个索引
        root.val = preorder[preStart];
        int p = instart;
        for (int i = instart; i <= endStart; i++) {
            if (root.val == inorder[i]) {
                p = i;
                break;
            }
        }
        int leftSize = p - instart;
        root.left = buildT(preorder, preStart + 1, preStart + leftSize, inorder, instart, p - 1);
        root.right = buildT(preorder, preStart + leftSize + 1, preEnd, inorder, p + 1, endStart);
        return root;
    }
    //从中序 后序 还原二叉树

    //从前序 后序 还原二叉树

    //

    //寻找重复子树 思路是后序遍历框架 拼接成字符串的方式判断重复
    Set<TreeNode> findDuplicateSubtrees(TreeNode root) {
        find(root);
        return list;
    }
    Map<String,Integer> set = new HashMap<>();
    Set<TreeNode> list = new HashSet<>();

    String find(TreeNode root){

        if(root == null) return "#";

        String s = find(root.left)+","+find(root.right)+","+root.val;
        if(set.containsKey(s)){
            if(set.get(s) == 1){
                list.add(root);
            }
            set.put(s,set.get(s)+1);
        }else {
            set.put(s,1);
        }
        return s;
    }

    // 把一棵二叉树序列化成字符串 [2,1,#,6,3,#,#]
    public String serialize(TreeNode root) {
        if(root == null){
            return "#";
        }
        return root.val+","+serialize(root.left)+","+serialize(root.right);
    }

    // 把先序遍历得出的字符串反序列化成二叉树[2,1,#,6,3,#,#]
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(",");
        LinkedList<String> list = new LinkedList<>();
        for(String str:nodes){
            list.add(str);
        }
        return deserialize(list);
    }
    //先序反序列化 必须先找到root节点
    public TreeNode deserialize(LinkedList<String> list){
        String s = list.removeFirst();
        if("#".equals(s)){
            return null;
        }
        TreeNode treeNode = new TreeNode();
        treeNode.val = Integer.parseInt(s);
        treeNode.left = deserialize(list);
        treeNode.right = deserialize(list);
        return treeNode;

    }





    private void t(TreeNode node1, TreeNode node2) {
        if (node1 == null || node2 == null) {
            return;
        }
        node1.right = node2;
    }

    public static void main(String[] args) {
//        TreeDemo treeDemo = new TreeDemo();
//        TreeNode deserialize = treeDemo.deserialize("1,2,4,#,#,#,3,2,4,#,#,#,4,#,#");
//        System.out.println(treeDemo.serialize(deserialize));
//        treeDemo.before(deserialize);
//        System.out.println();
//        treeDemo.before1(deserialize);
//        System.out.println();
//        treeDemo.before2(deserialize);
//        System.out.println();
//        treeDemo.mid(deserialize);
//        System.out.println();
//        treeDemo.mid1(deserialize);
//        //后序
//        treeDemo.after(deserialize);
        int[][] i = new int[2][5];
        System.out.println(i.length+":::"+i[0].length);
//        Set<TreeNode> nodes = treeDemo.findDuplicateSubtrees(deserialize);
//        System.out.println(nodes);
    }

}
